//全排列
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[7];
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }
        
        for(size_t i = 0 ; i < nums.size() ; ++i)
        {
            if(check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
      dfs(nums);
      return ret;
    }
};

//子集
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    void dfs(vector<int>& nums,size_t pos)
    {
        ret.push_back(path);

        for(size_t i = pos ; i < nums.size() ; ++i)
        {
            path.push_back(nums[i]);
            dfs(nums,i+1);
            //恢复现场
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);
        return ret;
    }
};

//找出所有自己的异或总和再求和
class Solution {
public:
    int sum = 0;
    int path;
    void dfs(vector<int>& nums , size_t pos)
    {
        //直接统计
        sum += path;
        for(size_t i = pos ; i < nums.size() ; ++i)
        {
            path ^= nums[i];
            dfs(nums,i+1);
            //恢复现场
            path ^= nums[i];
        }
    }
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return sum;
    }
};

//全排列II
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    bool check[10];
    void dfs(vector<int>& nums)
    {
        if(path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for(size_t i = 0 ; i < nums.size() ; ++i)
        {
            if(check[i] == true || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false))
            {   
                continue;
            }
            else
            {
                    path.push_back(nums[i]);
                    check[i] = true;
                    dfs(nums);
                    check[i] = false;
                    path.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin() , nums.end());
        dfs(nums);
        return ret;
    }
};


